import java.util.*;

public class Solution692 {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> mark=new HashMap<>();
        for (String word:words) {
            int tmpCount=mark.getOrDefault(word,0);
            mark.put(word,tmpCount+1);
        }
        Set<String>[] sortedMark= new Set[words.length+1];
        for (Map.Entry et:mark.entrySet()) {
            int loc=(Integer) et.getValue();
            if(sortedMark[loc]==null){
                sortedMark[loc]=new TreeSet<>();
            }
            sortedMark[loc].add((String) et.getKey());
        }
        List<String> result=new LinkedList<>();
        outter:for (int i = words.length; i >= 0; i--) {
            Set<String> tmpSet=sortedMark[i];
            if(tmpSet==null){
                continue;
            }
            for (String tmpStr:tmpSet) {
                if(result.size()==k){
                    break outter;
                }
                result.add(tmpStr);
            }
        }
        return result;
    }
}
